<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/myblog/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/myblog/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/myblog/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/myblog/images/logo.svg" color="#222">

<link rel="stylesheet" href="/myblog/css/main.css">


<link rel="stylesheet" href="/myblog/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/myblog/lib/pace/pace-theme-minimal.min.css">
  <script src="/myblog/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"gao-qianwei.gitee.io","root":"/myblog/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="一、题目描述&amp;ensp;&amp;ensp;&amp;ensp;&amp;ensp;设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针&#x2F;引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。">
<meta property="og:type" content="article">
<meta property="og:title" content="设计链表">
<meta property="og:url" content="https://gao-qianwei.gitee.io/myblog/2021/04/30/%E9%93%BE%E8%A1%A8%EF%BC%9A%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8%EF%BC%88%E5%8D%95%E9%93%BE%E8%A1%A8%EF%BC%89/index.html">
<meta property="og:site_name" content="学无止境">
<meta property="og:description" content="一、题目描述&amp;ensp;&amp;ensp;&amp;ensp;&amp;ensp;设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针&#x2F;引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-04-30T15:20:53.536Z">
<meta property="article:modified_time" content="2021-04-30T15:39:41.465Z">
<meta property="article:author" content="高乾威">
<meta property="article:tag" content="leetcode">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="链表">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://gao-qianwei.gitee.io/myblog/2021/04/30/%E9%93%BE%E8%A1%A8%EF%BC%9A%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8%EF%BC%88%E5%8D%95%E9%93%BE%E8%A1%A8%EF%BC%89/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>设计链表 | 学无止境</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/myblog/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">学无止境</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/myblog/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/myblog/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/myblog/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/myblog/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/myblog/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/myblog/links/" rel="section"><i class="fa fa-link fa-fw"></i>友链</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://gao-qianwei.gitee.io/myblog/2021/04/30/%E9%93%BE%E8%A1%A8%EF%BC%9A%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8%EF%BC%88%E5%8D%95%E9%93%BE%E8%A1%A8%EF%BC%89/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/myblog/images/avatar.png">
      <meta itemprop="name" content="高乾威">
      <meta itemprop="description" content="报我楼成秋望月，把君诗读夜回灯">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="学无止境">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          设计链表
        </h1>

        <div class="post-meta">

          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-04-30 23:20:53 / 修改时间：23:39:41" itemprop="dateCreated datePublished" datetime="2021-04-30T23:20:53+08:00">2021-04-30</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/myblog/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
                </span>
                  ，
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/myblog/categories/%E7%AE%97%E6%B3%95/%E9%93%BE%E8%A1%A8/" itemprop="url" rel="index"><span itemprop="name">链表</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
            <span class="post-meta-divider">|</span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h3 id="一、题目描述"><a href="#一、题目描述" class="headerlink" title="一、题目描述"></a>一、题目描述</h3><p>&ensp;&ensp;&ensp;&ensp;设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。</p>
<span id="more"></span>

<p>&ensp;&ensp;&ensp;&ensp;在链表类中实现这些功能：</p>
<p>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。</p>
<p>&ensp;&ensp;&ensp;&ensp;示例：</p>
<pre><code>MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-&gt; 2-&gt; 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-&gt; 3
linkedList.get(1);            //返回3
</code></pre>
<p>&ensp;&ensp;&ensp;&ensp;提示：</p>
<p>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;所有val值都在 [1, 1000] 之内。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;操作次数将在  [1, 1000] 之内。<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;请不要使用内置的 LinkedList 库。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyLinkedList</span> &#123;</span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line">    <span class="built_in">MyLinkedList</span>() &#123;</span><br><span class="line">       </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtHead</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">       </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Append a node of value val to the last element of the linked list. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtTail</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtIndex</span><span class="params">(<span class="keyword">int</span> index, <span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Delete the index-th node in the linked list, if the index is valid. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">deleteAtIndex</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Your MyLinkedList object will be instantiated and called as such:</span></span><br><span class="line"><span class="comment"> * MyLinkedList* obj = new MyLinkedList();</span></span><br><span class="line"><span class="comment"> * int param_1 = obj-&gt;get(index);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtHead(val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtTail(val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtIndex(index,val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;deleteAtIndex(index);</span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>
<h3 id="二、解题思路"><a href="#二、解题思路" class="headerlink" title="二、解题思路"></a>二、解题思路</h3><p>&ensp;&ensp;&ensp;&ensp;首先定义链表节点（Node）的结构，它有一个值val，和指向下个节点的指针<em>next；故有Node(int x):val(x),next(NULL){}：定义一个节点，它的值为x，下个节点为空。<br>&ensp;&ensp;&ensp;&ensp;链表的属性、成员有链表的长度（size），指向链表头结点的指针（</em>dummy），其作用域标记为private。<br>&ensp;&ensp;&ensp;&ensp; MyLinkedList() ，初始化一个链表，长度为0，只有个dummy。<br>&ensp;&ensp;&ensp;&ensp;get(index)：先判断index是否有效：index&gt;(size-1)||index&lt;0则无效，然后生成一个指针，移到目标节点即可。<br>&ensp;&ensp;&ensp;&ensp;addAtHead(val)：初始化一个节点head，将head指向头节点，dummy指向head。<br>&ensp;&ensp;&ensp;&ensp;addAtTail(val)：遍历到尾节点，加上去即可<br>&ensp;&ensp;&ensp;&ensp;addAtIndex(index,val)：先判断index是否有效：size&lt;index则返回空值；然后将指针移到第 index 个节点之前的那个节点，插入即可（使之成为第index个节点）<br>&ensp;&ensp;&ensp;&ensp;deleteAtIndex(index)：先判断index是否有效：index&gt;=size||index&lt;0则返回空值；然后将指针移到第 index 个节点之前的那个节点，删除后面那个节点，再连接后面节点的后面节点即可。（老套娃了🐶🐶🐶）</p>
<h5 id="全场最佳：将指针移到第-index-个节点之前的那个节点"><a href="#全场最佳：将指针移到第-index-个节点之前的那个节点" class="headerlink" title="全场最佳：将指针移到第 index 个节点之前的那个节点"></a>全场最佳：将指针移到第 index 个节点之前的那个节点</h5><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//index从0开始，第一个结点的index为0，题目是这么要求的🐶</span></span><br><span class="line">	Node *head=dummy;</span><br><span class="line">      <span class="keyword">while</span>(index--)&#123;</span><br><span class="line">          head=head-&gt;next;</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>

<h3 id="三、我的代码"><a href="#三、我的代码" class="headerlink" title="三、我的代码"></a>三、我的代码</h3><p>&ensp;&ensp;&ensp;&ensp;直接在力扣上写的。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyLinkedList</span> &#123;</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">Node</span>&#123;</span></span><br><span class="line">        <span class="keyword">int</span> val;</span><br><span class="line">        Node *next;</span><br><span class="line">        <span class="built_in">Node</span>(<span class="keyword">int</span> x):<span class="built_in">val</span>(x),<span class="built_in">next</span>(<span class="literal">NULL</span>)&#123;&#125;</span><br><span class="line">    &#125;;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="keyword">int</span> size;</span><br><span class="line">    Node *dummy;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line">    <span class="built_in">MyLinkedList</span>() &#123;</span><br><span class="line">        dummy=<span class="keyword">new</span> <span class="built_in">Node</span>(<span class="number">0</span>);</span><br><span class="line">        size=<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(index&gt;(size<span class="number">-1</span>)||index&lt;<span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        Node *head=dummy-&gt;next;</span><br><span class="line">        <span class="keyword">while</span>(index--)&#123;</span><br><span class="line">            head=head-&gt;next;            </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> head-&gt;val;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtHead</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        Node *head=<span class="keyword">new</span> <span class="built_in">Node</span>(val);</span><br><span class="line">        head-&gt;next=dummy-&gt;next;</span><br><span class="line">        dummy-&gt;next=head;</span><br><span class="line">        size++;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Append a node of value val to the last element of the linked list. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtTail</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        Node *tailNode=dummy;</span><br><span class="line">        Node *newTailNode=<span class="keyword">new</span> <span class="built_in">Node</span>(val);</span><br><span class="line">        <span class="keyword">while</span>(tailNode-&gt;next!=<span class="literal">NULL</span>)&#123;</span><br><span class="line">            tailNode=tailNode-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        tailNode-&gt;next=newTailNode;</span><br><span class="line">        size++;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addAtIndex</span><span class="params">(<span class="keyword">int</span> index, <span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(size&lt;index)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        Node *head=dummy;</span><br><span class="line">        Node *t=<span class="keyword">new</span> <span class="built_in">Node</span>(val);</span><br><span class="line">        <span class="keyword">while</span>(index--)&#123;</span><br><span class="line">            head=head-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        t-&gt;next=head-&gt;next;</span><br><span class="line">        head-&gt;next=t;</span><br><span class="line">        size++;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Delete the index-th node in the linked list, if the index is valid. */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">deleteAtIndex</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(index&gt;=size||index&lt;<span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        Node *head=dummy;</span><br><span class="line">        <span class="keyword">while</span>(index--)&#123;</span><br><span class="line">            head=head-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        Node *t=head-&gt;next;</span><br><span class="line">        head-&gt;next=head-&gt;next-&gt;next;</span><br><span class="line">        <span class="keyword">delete</span> t;</span><br><span class="line">        size--;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Your MyLinkedList object will be instantiated and called as such:</span></span><br><span class="line"><span class="comment"> * MyLinkedList* obj = new MyLinkedList();</span></span><br><span class="line"><span class="comment"> * int param_1 = obj-&gt;get(index);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtHead(val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtTail(val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;addAtIndex(index,val);</span></span><br><span class="line"><span class="comment"> * obj-&gt;deleteAtIndex(index);</span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>
    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/myblog/tags/leetcode/" rel="tag"># leetcode</a>
              <a href="/myblog/tags/%E7%AE%97%E6%B3%95/" rel="tag"># 算法</a>
              <a href="/myblog/tags/%E9%93%BE%E8%A1%A8/" rel="tag"># 链表</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/myblog/2021/04/30/%E9%93%BE%E8%A1%A8%EF%BC%9A%E6%89%81%E5%B9%B3%E5%8C%96%E5%A4%9A%E7%BA%A7%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/" rel="prev" title="扁平化多级双向链表">
      <i class="fa fa-chevron-left"></i> 扁平化多级双向链表
    </a></div>
      <div class="post-nav-item">
    <a href="/myblog/2021/05/01/makedown%EF%BC%9Amakedown%E8%AF%AD%E6%B3%95/" rel="next" title="makedown语法">
      makedown语法 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%80%E3%80%81%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">一、题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E3%80%81%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">二、解题思路</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#%E5%85%A8%E5%9C%BA%E6%9C%80%E4%BD%B3%EF%BC%9A%E5%B0%86%E6%8C%87%E9%92%88%E7%A7%BB%E5%88%B0%E7%AC%AC-index-%E4%B8%AA%E8%8A%82%E7%82%B9%E4%B9%8B%E5%89%8D%E7%9A%84%E9%82%A3%E4%B8%AA%E8%8A%82%E7%82%B9"><span class="nav-text">全场最佳：将指针移到第 index 个节点之前的那个节点</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%89%E3%80%81%E6%88%91%E7%9A%84%E4%BB%A3%E7%A0%81"><span class="nav-text">三、我的代码</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="高乾威"
      src="/myblog/images/avatar.png">
  <p class="site-author-name" itemprop="name">高乾威</p>
  <div class="site-description" itemprop="description">报我楼成秋望月，把君诗读夜回灯</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/myblog/archives/">
        
          <span class="site-state-item-count">91</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/myblog/categories/">
          
        <span class="site-state-item-count">27</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/myblog/tags/">
          
        <span class="site-state-item-count">59</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="http://github.com/GaoQianwei" title="GitHub → http:&#x2F;&#x2F;github.com&#x2F;GaoQianwei" rel="noopener" target="_blank">GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:2966807184@qq.com" title="E-Mail → mailto:2966807184@qq.com" rel="noopener" target="_blank">E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.zhihu.com/people/xue-wu-zhi-jing-75-22" title="知乎 → https:&#x2F;&#x2F;www.zhihu.com&#x2F;people&#x2F;xue-wu-zhi-jing-75-22" rel="noopener" target="_blank">知乎</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://blog.csdn.net/weixin_45341339" title="CSDN → https:&#x2F;&#x2F;blog.csdn.net&#x2F;weixin_45341339" rel="noopener" target="_blank">CSDN</a>
      </span>
  </div>



      </div><div>
  <canvas id="canvasDiyBlock" style="width:60%;">当前浏览器不支持canvas，请更换浏览器后再试</canvas>
<script src="/myblog/js/custom/clock.js"></script>

</div>


    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2021-04 到 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">高乾威</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

<span class="post-meta-divider">|</span>

<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">全站共 117.2k 字</span>
</div>

<span class="post-meta-divider">|</span>
        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/myblog/lib/anime.min.js"></script>
  <script src="/myblog/lib/velocity/velocity.min.js"></script>
  <script src="/myblog/lib/velocity/velocity.ui.min.js"></script>

<script src="/myblog/js/utils.js"></script>

<script src="/myblog/js/motion.js"></script>


<script src="/myblog/js/schemes/pisces.js"></script>


<script src="/myblog/js/next-boot.js"></script>


  <script defer src="/myblog/lib/three/three.min.js"></script>
    <script defer src="/myblog/lib/three/canvas_lines.min.js"></script>


  




  
<script src="/myblog/js/local-search.js"></script>













  

  

</body>
</html>
